"""
给定数组nums，以及阈值threshold
找一个最小的除数，使得数组元素除以除数之后的商的和小于等于阈值
除法向上取整
很明显二分除数，然后对于给定的除数检查是否满足条件即可, O(NlogN)
"""
import bisect
from typing import List
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def check(mid: int) -> bool:
            ans = 0
            for ai in nums:
                ans += Solution.div(ai, mid)
            return ans <= threshold

        # 首先定义数组A[1, 2, ..., N]
        # 然后定义check函数使得数组前半段都返回0，后半段都返回1
        # key选项在3.10及其以后才有
        # 然后在数组上二分找到最左边的1的位置，记作p，则A[p]就是满足条件的最小值
        ans = bisect.bisect_left(range(1, max(nums) + 1), 1, key=lambda x: 1 if check(x) else 0)
        return ans + 1

    @staticmethod
    def div(a: int, b: int) -> int:
        if 0 == a % b: return a // b
        return a // b + 1